package test;
import java.util.*;

/**
 * 描述：
 * 数组的相对排序
 * @author hl
 * @version 1.0
 * @date 2020/11/14 15:46
 */
public class RelativeSortArray {
    public int[] relativeSortArray3(int[] arr1, int[] arr2) {
        int maxLenght = Integer.MIN_VALUE;
        for (int i : arr1) {
            maxLenght = Math.max(maxLenght, i);
        }
        int fre[] = new int[maxLenght + 1];
        for (int i : arr1) {
            fre[i]++;
        }
        int[] res = new int[arr1.length];
        int index = 0;
        for (int i : arr2) {
            for (int j = 0; j < fre[i];j++) {
                res[index++] = i;
            }
            fre[i] = 0;
        }
        for (int i = 0; i < fre.length; i++) {
            for (int j = 0; j < fre[i]; j++) {
                res[index++] = i;
            }
        }
        return res;
    }


    public int[] relativeSortArray2(int[] arr1, int[] arr2) {
        List<Integer> list = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i);
        }
        for (Integer item : arr1) {
            list.add(item);
        }
        Collections.sort(list, (o1, o2) -> {
            if (map.containsKey(01) || map.containsKey(02)) {
                return map.getOrDefault(o1, 1001) - map.getOrDefault(o2, 1001);
            }
            return o1 - o2;
        });
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = list.get(i);
        }
        return arr1;
    }
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i);
        }
        for (int i = 0; i < arr1.length; i++) {
            Integer indexI = map.get(arr1[i]);
            for (int j = i - 1; j >= 0 && indexI != null; j--) {
                if (map.containsKey(arr1[j]) && indexI >= map.get(arr1[j])) {
                    break;
                }
                int temp = arr1[j];
                arr1[j] = arr1[j + 1];
                arr1[j + 1] = temp;
            }
        }
        for (int i = arr1.length - 1; arr1[i] != arr2[arr2.length - 1]; i--) {
            for (int j = i - 1; arr1[j] != arr2[arr2.length - 1] && arr1[j] > arr1[j + 1]; j--) {
                int temp = arr1[j];
                arr1[j] = arr1[j + 1];
                arr1[j + 1] = temp;
            }
        }
        return arr1;
    }

    public static void main(String[] args) {
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        new RelativeSortArray().relativeSortArray(arr1, arr2);
    }
}
